package com.practice.niuke.new_direct_practice.class02;

public class Code04_MaxSumInTree {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            value = val;
        }
    }

    public static int maxSum = Integer.MIN_VALUE;

    public static int maxPath(Node head) {
        p(head, 0);
        return maxSum;
    }

    public static void p(Node x, int pre) {
        if (x.left == null && x.right == null) {
            maxSum = Math.max(maxSum, pre + x.value);
        }
        if (x.left != null) {
            p(x.left, pre + x.value);
        }
        if (x.right != null) {
            p(x.right, pre + x.value);
        }
    }


    public static int maxDis(Node head) {
        if (head == null) {
            return 0;
        }
        return process2(head);
    }

    // x为头的整棵树上，最大路径和是多少，返回。
    // 路径要求，一定从x出发，到叶节点，算做一个路径
    public static int process2(Node x) {
        if (x.left == null && x.right == null) {
            return x.value;
        }
        int next = Integer.MIN_VALUE;
        if (x.left != null) {
            next = process2(x.left);
        }
        if (x.right != null) {
            next = Math.max(next, process2(x.right));
        }
        return x.value + next;
    }


    /**
     * 信息体
     */
    public static class Info {
        public int headWalkToLeafMaxPathSum;

        public Info(int sum) {
            headWalkToLeafMaxPathSum = sum;
        }
    }

    /**
     * 递归函数
     *
     * @param x
     * @return
     */
    public static Info process(Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int p1 = 0;
        int p2 = 0;
        int p3 = x.value;
        if (leftInfo != null) {// 左边有树
            p1 = x.value + leftInfo.headWalkToLeafMaxPathSum;
        }
        if (rightInfo != null) {
            p2 = x.value + rightInfo.headWalkToLeafMaxPathSum;
        }
        if (x.left == null && x.right == null) {
            return new Info(p3);
        }
        if (x.left != null && x.right != null) {
            return new Info(Math.max(p1, p2));
        }
        // 一定是一个为空，另一个不为空
        return new Info(x.left != null ? p1 : p2);
    }

    /**
     * 调用递归函数的主函数
     *
     * @param head
     * @return
     */
    public static int maxPathSum(Node head) {
        return process(head).headWalkToLeafMaxPathSum;
    }


    public static void main(String[] args) {


    }

}
